package com.zwj.interview.单调队列;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author: Zwj
 * @Date: 2022/2/28 13:34
 * 输入一个数组nums和一个正整数k，有一个大小为k的窗口在nums上从左至右滑动，请输出每次滑动时窗口中的最大值
 * 单调队列解法：
 * https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/hua-dong-chuang-kou-de-zui-da-zhi-by-lee-ymyo/
 */
public class 滑动窗口中的最大值 {

    class MonotonicQueue {
        LinkedList<Integer> q = new LinkedList<>();
        //每次添加元素的时候都和队尾的元素进行比较，如果大于队尾的元素，就将队尾的元素弹出去，直到队列为空
        //这样做的结果就是队首的元素就是最大的，也就是严格单调递减的
        public void push(int n) {
            while (!q.isEmpty() && q.getLast() < n) {
                q.pollLast();
            }
            q.addLast(n);
        }
        //队头元素最大
        public int max() {
            return q.getFirst();
        }
        public void pop(int n) {
            if (n == q.getFirst()) {
                q.pollFirst();
            }
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue window = new MonotonicQueue();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {
                window.push(nums[i]);
            } else {
                //向前滑动窗口
                window.push(nums[i]);
                //记录当前窗口的最大值
                res.add(window.max());
                //移除窗口中最老的数字
                window.pop(nums[i - k + 1]);
            }
        }
        int[] arr = res.stream().mapToInt(Integer::intValue).toArray();
        return arr;
    }



}